Search results for " Parsing"

Computing the Original eBWT Faster, Simpler, and with Less Memory

2021

Mantaci et al. [TCS 2007] defined the \(\mathrm {eBWT}\) to extend the definition of the \(\mathrm {BWT}\) to a collection of strings. However, since this introduction, it has been used more generally to describe any \(\mathrm {BWT}\) of a collection of strings, and the fundamental property of the original definition (i.e., the independence from the input order) is frequently disregarded. In this paper, we propose a simple linear-time algorithm for the construction of the original \(\mathrm {eBWT}\), which does not require the preprocessing of Bannai et al. [CPM 2021]. As a byproduct, we obtain the first linear-time algorithm for computing the \(\mathrm {BWT}\) of a single string that uses …

Natural Language Parsing

2009

Automatic natural language processing captures a lion’s share of the attention in open information management. In one way or another, many applications have to deal with natural language input. In this chapter the authors investigate the problem of natural language parsing from the perspective of biolinguistics. They argue that the human mind succeeds in the parsing task without the help of languagespecific rules of parsing and language-specific rules of grammar. Instead, there is a universal parser incorporating a universal grammar. The main argument comes from language acquisition: Children cannot learn language specific parsing rules by rule induction due to the complexity of unconstrain…

SAP UI5 lietotņu pirmkoda automatizētas pārstrādes rīka izstrāde

2018

Kvalifikācijas darbā tika izstrādāts rīks SAP UI5 lietotņu pirmkoda automatizētai pārveidei, kas veic SAP UI5 JavaScript koda analīzi un aizvieto novecojušās un mazāk efektīvās sinhronās moduļu ielādes metodes ar aktuālajām un tīmekļa kontekstā efektīvākām asinhronajām moduļu ielādes metodēm, kā arī veic koda izmaiņas, kuru nepieciešamība izriet no iepriekšminētās metožu aizvietošanas. Izstrādātā rīka mērķis ir padarīt automātisku, ātru un pabeigtu, bez cilvēciskām kļūdām, šādas pārstrādes procesu tām lietotnēm un projektiem, kuru izstrāde ir aizsākusies pietiekami sen, lai kodu būtu nepieciešams šādi aktualizēt. Rīks tika izstrādāts izmantojot SAP UI5 ietvaru lietotāja saskarnes pusē, Node…

The complexity of graph languages generated by hyperedge replacement

1990

Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.

3D Object Modeling by Sharing Visual Attributes across Poses and Scales

2014

Scene parsing aims at understanding a scene and the arrangements of the objects in it. While this is a task human beings are pretty good at [7], a machine needs to: recognize the kind of scene (indoor vs outdoor, bedroom vs. living room etc.)[4], detect and recognize 3D objects across multiple poses and scales [8, 5], infer the geometrical arrangement of the objects in the scene [2, 1], etc.. In the proposed framework, a 3D object is modeled as a graph. Each node in the graph represents a visual attribute automatically discovered by considering features that are consistently and repeatedly present across different poses and scales. Such visual attributes are different from “parts” [5], whic…

Metodo e apparato per la compressione e la decompressione dati tramite il quale si possono utilizzare efficientemente molteplici compressori e decomp…

2010

Optimal Parsing for Dictionary-Based Compression

2013

Dictionary-based compression algorithms include a parsing strategy to transform the input text into a sequence of dictionary phrases. Given a text, such process usually is not unique and, for compression purposes, it makes sense to find one of the possible parsing that minimise the final compression ratio. This is the parsing problem. In more than 30 years of history of dictionary-based text compression only few optimal parsing algorithms were presented. Most of the practical dictionary-based compression solutions need or prefer to factorise the input data into a sequence of dictionary-phrases and symbols. Those two output categories are usually encoded via two different encoders producing …

A combined semantic-syntactic sentence analysis for students assessment

2010

TutorJ is an Intelligent Tutoring System able to fulfill the requests of a student with a learning path inside didactical materials. To this aim, it must assess the level of training of the learner. In the first version of TutorJ this goal was reached through a conversational agent whose linguistic interaction enriched by a LSA-based text analysis. This approach suffers from the limitations of LSA as a bag-of- words approach. Next, morphosyntactic comparison of sentences' structures was implemented. In this paper we present a new version of the assessment procedure involving both semantic, and morphosyntactic analysis user's sentences.

On parsing optimality for dictionary-based text compression—the Zip case

2013

Dictionary-based compression schemes are the most commonly used data compression schemes since they appeared in the foundational paper of Ziv and Lempel in 1977, and generally referred to as LZ77. Their work is the base of Zip, gZip, 7-Zip and many other compression software utilities. Some of these compression schemes use variants of the greedy approach to parse the text into dictionary phrases; others have left the greedy approach to improve the compression ratio. Recently, two bit-optimal parsing algorithms have been presented filling the gap between theory and best practice. We present a survey on the parsing problem for dictionary-based text compression, identifying noticeable results …

Dictionary-symbolwise flexible parsing

2012

AbstractLinear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) that works when the dictionary is prefix closed and the encoding of dictionary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionaries and any symbolwise compressor under some natural hypothesis. In the case of LZ78-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbol…